package leetcode101.complex_datastructure;

/**
 * @author Synhard
 * @version 1.0
 * @class DSUNumber
 * @description TODO
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-02 14:55
 */
public class DSU {
    private int[] parent;
    private int[] number; // 每个集合的个数

    public DSU(int n) {
        parent = new int[n];
        number = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            number[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public void union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (number[rootX] <= number[rootY]) {
            parent[rootX] = rootY;
            number[rootY] += number[rootX];
        } else {
            parent[rootY] = rootX;
            number[rootX] += number[rootY];
        }
    }
}
